//	--------------------------------------------------------------------
//	Copyright(C) 2006,2007 Zhao Yukun. All rights reserved.
//	This file is a part of the Xeres system.
//	Xeres 2007
//	Contact : xeres.engine@gmail.com
//	$(reservedInfo)
//	$(reservedDeclaration)
//	--------------------------------------------------------------------
///	@file	<dep_map.inl>
///	@path	~/src/lib/utilities/
///	@date	2007/06/19
///	@desc	dependency map.

#pragma once

#include "lib/utilities/debug.h"
#include "lib/utilities/dep_map.h"

#define	DEPMAP_DEBUG		0

#define	ID_FACTOR			1000

namespace xeres {

	template<typename _NodeType> inline dep_map<_NodeType>::_Node::_Node( void )
		: m_content()
		, m_next( NULL )
		, m_name( NULL )
		, m_visit( NOT_VISITED )
		, m_id( INVALID_NODE_ID )
	{
		m_next = this;
	}
	template<typename _NodeType> inline dep_map<_NodeType>::_Node::_Node( const _Node& n )
		: m_content( n.m_content )
		, m_next( n.m_next )
		, m_name( n.m_name )
		, m_visit( n.m_visit )
		, m_id( n.m_id )
		, m_dep( n.m_dep )
	{
	}

	// get next node
	template<typename _NodeType> inline typename dep_map<_NodeType>::_Node * dep_map<_NodeType>::_Node::get_next( void )
	{
		return m_next;
	}

	// determine if node is tail
	template<typename _NodeType> inline bool dep_map<_NodeType>::_Node::is_tail( void ) const
	{
		return (m_next == NULL);
	}

	// clear node visit info
	template<typename _NodeType> inline void dep_map<_NodeType>::_Node::clear_visit( void )
	{
		m_visit = NOT_VISITED;
		m_id = INVALID_NODE_ID;
		m_next = this;
	}

	// set visit
	template<typename _NodeType> inline void dep_map<_NodeType>::_Node::set_visit( bool visting )
	{
		m_visit = visting ? VISITING : VISITED;
	}

	// determine if node is not visited
	template<typename _NodeType> inline bool dep_map<_NodeType>::_Node::is_not_visited( void ) const
	{
		return m_visit == NOT_VISITED;
	}

	// determine if node is visiting
	template<typename _NodeType> inline bool dep_map<_NodeType>::_Node::is_visiting( void ) const
	{
		return m_visit == VISITING;
	}

	// determine if node is visited
	template<typename _NodeType> inline bool dep_map<_NodeType>::_Node::is_visited( void ) const
	{
		return m_visit == VISITED;
	}

	// ctor
	template<typename _NodeType> inline dep_map<_NodeType>::_Node::_NodeVisiteGuard::_NodeVisiteGuard( _Node& tn )
		: m_tn( tn )
	{
		m_tn.set_visit( true );
	}
	// dtor
	template<typename _NodeType> inline dep_map<_NodeType>::_Node::_NodeVisiteGuard::~_NodeVisiteGuard( void )
	{
		m_tn.set_visit( false );
	}

	// ctor
	template<typename _NodeType> inline dep_map<_NodeType>::dep_map( void )
		: m_nodeRoot( NULL )
	{
	}

	// dtor
	template<typename _NodeType> inline dep_map<_NodeType>::~dep_map( void )
	{
	}

	// add node
	template<typename _NodeType> inline void dep_map<_NodeType>::add_node(
		const _NodeType& content , const WString& name , const WString& dependency )
	{
		// clear node root to guarantee nodes will be sort again
		m_nodeRoot = NULL;

		// add node and build its dependency
		if( m_nodeMap.has_key( name ) )
		{
			TRACE_ERROR( _S("dep_map::add_node: Conflict node '%s' (node exists).") , name.c_str() );
			return;
		}

		// create new node entry
		_Node tn;
		tn.m_content = content;
		tn.m_dep = dependency;
		tn.clear_visit();

		// insert node
		m_nodeMap.insert( name , tn );

		// retrieve name
		NodeMap::iterator it = m_nodeMap.find( name );
		_Node& n = it->second;
		n.m_name = &(it->first);

#if DEPMAP_DEBUG
		TRACE_DEBUG( _S("dep_map::add_node: Added node '%s'.") , name.c_str() );
#endif // DEPMAP_DEBUG
	}

	// sort nodes
	template<typename _NodeType> inline bool dep_map<_NodeType>::sort_nodes( void )
	{
		// clear tags
		for( NodeMap::iterator it = m_nodeMap.begin() ; it != m_nodeMap.end() ; ++it )
		{
			_Node& tn = it->second;
			tn.clear_visit();
		}

		int visited = 0;

		// for all not-traversed nodes
		for( NodeMap::iterator it = m_nodeMap.begin() ; it != m_nodeMap.end() ; ++it )
		{
			_Node& tn = it->second;

			if( tn.is_not_visited() )
			{
				// failed if traversal has error
				if( !traversal_dep( tn , visited ) )
					return false;
			}
		}

		// visited check
		assert( visited == m_nodeMap.size() );

		return true;
	}

	// build dependency
	template<typename _NodeType> inline bool dep_map<_NodeType>::build_dep( const WString& dep , std::vector< _Node * >& dep_nodes )
	{
		std::vector< WString > spec;
		// count dependency
		size_t start = 0 , end = 0;
		for( ; end < dep.size() ; ++end )
		{
			// separated by DEP_SEPARATOR
			if( dep[end] == DEP_SEPARATOR )
			{
				if( end - start > 0 )
				{
					WString str = dep.substr( start , end );
					if( !str.empty() )
						spec.push_back( dep.substr( start , end ) );
				}
				start = end + 1;
			}
		}
		// the last one
		if( end - start > 0 )
		{
			WString str = dep.substr( start , end );
			if( !str.empty() )
				spec.push_back( str );
		}

		// for all dependencies
		dep_nodes.resize( spec.size() );

		for( size_t i = 0 ; i < spec.size() ; ++i )
		{
			NodeMap::iterator it = m_nodeMap.find( spec[i] );
			if( it == m_nodeMap.end() )
			{
				// node not found!
				TRACE_ERROR( _S("dep_map::build_dep: Depended node not found '%s'.") , spec[i].c_str() );
				return false;
			}
			dep_nodes[i] = ( &(it->second) );
		}
		return true;
	}

	// traversal dependency
	template<typename _NodeType> inline bool dep_map<_NodeType>::traversal_dep( _Node& tn , int& visited )
	{
		const WString& dep = tn.m_dep;

		// visit check
		if( tn.is_visiting() )
		{
			// cycle dependency
			TRACE_ERROR( _S("dep_map::traversal_dep: Cycle dependency on module '%s' (dep '%s').") ,
				tn.m_name->c_str() , tn.m_dep.c_str() );
			return false;
		}
		else if( tn.is_visited() )
		{
			return true;
		}

		// not visited
		assert( tn.is_not_visited() );

		// visit!

		_Node::_NodeVisiteGuard __nodeGuard( tn );

		// dispatch by dependency
		if( dep.empty() )
		{
			// no dependency , just insert as root
			insert_root( tn , visited );
		}
		else
		{
			std::vector< _Node * > dep_nodes;

			if( !build_dep( tn.m_dep , dep_nodes ) )
				return false;

			if( dep_nodes.size() == 0 )
			{
				// maybe all null dependency, insert as root
				insert_root( tn , visited );
			}
			else
			{
				// traversal all nodes
				for( size_t i = 0 ; i < dep_nodes.size() ; ++i )
				{
					if( !traversal_dep( *(dep_nodes[i]) , visited ) )
						return false;
				}

				// insert after largest id
				_Node * most_dep = dep_nodes[0];
				for( size_t i = 1 ; i < dep_nodes.size() ; ++i )
				{
					if( most_dep->m_id < dep_nodes[i]->m_id )
						most_dep = dep_nodes[i];
				}

				insert_after( tn , most_dep , visited );
			}
		}

		// increase visited count
		++visited;

#if DEPMAP_DEBUG

		TRACE_DEBUG( _S("dep_map::traversal_dep: after traversal %s: \n") , tn.m_name->c_str() );
		// run one by one
		_Node * node = m_nodeRoot;
		while( node )
		{
			TRACE_DEBUG( _S(" [%s:(%i)]\n") , node->m_name->c_str() , node->m_id );
			node = node->get_next();
		}
#endif

		return true;
	}

	// insert as root node
	template<typename _NodeType> inline void dep_map<_NodeType>::insert_root( _Node& tn , int visited )
	{
		if( m_nodeRoot == NULL )
		{
			// just assign
			m_nodeRoot = &tn;
			tn.m_id = 0;
			tn.m_next = NULL;
		}
		else
		{
			int rest = ( (int)m_nodeMap.size() - visited );
			tn.m_id = m_nodeRoot->m_id - ( rest * ID_FACTOR );
			tn.m_next = m_nodeRoot;
			m_nodeRoot = &tn;
		}
	}

	// insert node after
	template<typename _NodeType> inline void dep_map<_NodeType>::insert_after( _Node& tn , _Node * after_this , int visited )
	{
		int rest = ( (int)m_nodeMap.size() - visited );

		// insert directly if nothing after after_this
		if( after_this->is_tail() )
		{
			tn.m_id = after_this->m_id + ( rest * ID_FACTOR );
			after_this->m_next = &tn;
			tn.m_next = NULL;
		}
		else
		{
			// see if id gap between after_this and m_next is valid
			int id_gap = abs( after_this->m_id - after_this->m_next->m_id );

			if( id_gap < 2 )
			{
				// no gap between ids, resort all
				resort_id();
			}

			tn.m_id = ( after_this->m_id + after_this->m_next->m_id ) / 2;

			tn.m_next = after_this->m_next;
			after_this->m_next = &tn;
		}
	}

	// resort all id
	template<typename _NodeType> inline void dep_map<_NodeType>::resort_id( void )
	{
		TRACE_WARNING( _S("dep_map::resort_id: Need to resort Id.") );

		int id = 0;
		// run one by one
		_Node * node = m_nodeRoot;
		while( node )
		{
			node->m_id = id;
			node = node->get_next();
			id += (int)m_nodeMap.size() * ID_FACTOR;
		}
	}

	// iterator
	
	// ctor
	template<typename _NodeType> inline dep_map<_NodeType>::iterator::iterator( void )
		: m_node( NULL )
	{
	}

	// ctor
	template<typename _NodeType> inline dep_map<_NodeType>::iterator::iterator( 
		typename dep_map<_NodeType>::_Node * node )
		: m_node( node )
	{
	}

	// copier
	template<typename _NodeType> inline dep_map<_NodeType>::iterator::iterator( const iterator& rhs )
		: m_node( rhs.m_node )
	{
	}

	// assignment
	template<typename _NodeType> inline typename dep_map<_NodeType>::iterator&
		dep_map<_NodeType>::iterator::operator = ( const iterator& rhs )
	{
		m_node = rhs.m_node;
		return *this;
	}

	// *
	template<typename _NodeType> inline typename _NodeType&
		dep_map<_NodeType>::iterator::operator * ( void )
	{
		assert( m_node );
		return (m_node->m_content);
	}

	// *
	template<typename _NodeType> inline typename const _NodeType&
		dep_map<_NodeType>::iterator::operator * ( void ) const
	{
		assert( m_node );
		return (m_node->m_content);
	}

	// ++ (prefix)
	template<typename _NodeType> inline typename dep_map<_NodeType>::iterator&
		dep_map<_NodeType>::iterator::operator ++ ( void )
	{
		m_node = m_node->get_next();
		return *this;
	}

	// ++ (postfix)
	template<typename _NodeType> inline typename dep_map<_NodeType>::iterator
		dep_map<_NodeType>::iterator::operator ++ ( int )
	{
		iterator it( m_node );
		m_node = m_node->get_next();
		return it;
	}

	// ==
	template<typename _NodeType> inline bool
		dep_map<_NodeType>::iterator::operator == ( const typename dep_map<_NodeType>::iterator& it ) const
	{
		return m_node == it.m_node;
	}

	// !=
	template<typename _NodeType> inline bool 
		dep_map<_NodeType>::iterator::operator != ( const typename dep_map<_NodeType>::iterator& it ) const
	{
		return m_node != it.m_node;
	}

	// get begin iterator
	template<typename _NodeType> inline typename dep_map<_NodeType>::iterator
		dep_map<_NodeType>::begin( void )
	{
		if( m_nodeRoot == NULL )
		{
			sort_nodes();
		}
		return iterator( m_nodeRoot );
	}

	// get end iterator
	template<typename _NodeType> inline typename dep_map<_NodeType>::iterator
		dep_map<_NodeType>::end( void )
	{
		return iterator();
	}

} // namespace xeres
